package demo4;

import demo8.Class_Tire;

import java.util.*;
public class Code02_TrieTree {

	//创建前缀树节点

	public static class Node{

		public int pass ;//经过这节点的次数
		public int end;//以这个字符为结尾的次数

		public Node[] nexts ;//多叉树,每个节点都会有很多条路

		//构造方法

		public Node(){
			this.pass = 0;
			this.end = 0;
			this.nexts = new Node[26];//可能会有26条路
		}

	}

	//创建一颗前缀树

	public static class Trie{

		private Node root ;//前缀树的根节点

		public Trie(){
			root = new Node();//创建前缀树这个根节点
		}

		//insert方法---将字符串插入到这颗前缀树中

		public  void insert(String words){
			if(words == null){
				return ;
			}
			char[] str = words.toCharArray();//将字符串转化成字符数组

			Node node = root;
			node.pass++;//经过这个节点了
			int path = 0;
			for(int i =0 ;i<str.length;++i){
				path = str[i] - 'a';//该往path这条路走
				if(node.nexts[path] == null){
					node.nexts[path] = new Node();//如果没有这条路就创建这条路
				}
				node = node.nexts[path];
				node.pass++;
			}
			node.end++;

		}

		//搜索这个单词words出现了几次
		public int search(String words){
			if(words == null) return 0;
			char[] str = words.toCharArray();

			Node node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = str[i] - 'a' ;//得到是哪条路

				if(node.nexts[path]==null){
					return 0;
				}
				node = node.nexts[path];
			}
			return node.end;
		}

		public int prefixNumber(String words){
			if(words == null){
				return 0;
			}
			char[] str = words.toCharArray();
			Node node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = str[i] - 'a';
				if(node.nexts[path] == null){
					return 0;
				}
				node = node.nexts[path];
			}
			return node.pass;
		}

		public void delete(String words){
			if(words == null) return ;

			if(search(words)!=0){
				char[] str = words.toCharArray();
				Node node = root;
				node.pass -- ;
				int path  = 0;
				for(int i = 0 ;i<str.length;++i){
					path = str[i] - 'a';
					if(--node.nexts[path].pass==0){
						node.nexts[path] = null;
						return;
					}
					node = node.nexts[path];
				}
				node.end--;
			}
		}

	}

//	public static class Node2 {//前缀树节点
//		public int pass;//经过这个节点的次数
//		public int end;
//		public HashMap<Integer, Node2> nexts;//利用哈希表来存储当前路和节点
//
//		public Node2() {//初始化节点
//			pass = 0;
//			end = 0;
//			nexts = new HashMap<>();
//		}
//	}

//	public static class Trie2 {
//		private Node2 root;//根节点
//
//		public Trie2() {//构造方法初始化
//			root = new Node2();
//		}
//
//		public void insert(String word) {
//			if (word == null) {
//				return;
//			}
//			char[] chs = word.toCharArray();
//			Node2 node = root;
//			node.pass++;
//			int index = 0;
//			for (int i = 0; i < chs.length; i++) {
//				index = (int) chs[i];
//				if (!node.nexts.containsKey(index)) {
//					node.nexts.put(index, new Node2());
//				}
//				node = node.nexts.get(index);
//				node.pass++;
//			}
//			node.end++;
//		}
//
//		public void delete(String word) {
//			if (search(word) != 0) {
//				char[] chs = word.toCharArray();
//				Node2 node = root;
//				node.pass--;
//				int index = 0;
//				for (int i = 0; i < chs.length; i++) {
//					index = (int) chs[i];
//					if (--node.nexts.get(index).pass == 0) {
//						node.nexts.remove(index);
//						return;
//					}
//					node = node.nexts.get(index);
//				}
//				node.end--;
//			}
//		}
//
//		// word这个单词之前加入过几次
//		public int search(String word) {
//			if (word == null) {
//				return 0;
//			}
//			char[] chs = word.toCharArray();
//			Node2 node = root;
//			int index = 0;
//			for (int i = 0; i < chs.length; i++) {
//				index = (int) chs[i];
//				if (!node.nexts.containsKey(index)) {
//					return 0;
//				}
//				node = node.nexts.get(index);
//			}
//			return node.end;
//		}
//
//		// 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
//		public int prefixNumber(String pre) {
//			if (pre == null) {
//				return 0;
//			}
//			char[] chs = pre.toCharArray();
//			Node2 node = root;
//			int index = 0;
//			for (int i = 0; i < chs.length; i++) {
//				index = (int) chs[i];
//				if (!node.nexts.containsKey(index)) {
//					return 0;
//				}
//				node = node.nexts.get(index);
//			}
//			return node.pass;
//		}
//	}

	public static class Node2{
		public int pass;
		public int end ;
		public HashMap<Integer, Node2> nexts;
		public Node2(){
			this.pass = 0;
			this.end = 0;
			this.nexts = new HashMap<>();
		}

	}

	public static class Tire2{
		private Node2 root;

		public Tire2(){
			this.root = new Node2();
		}

		public void insert(String words){
			if(words==null) return;
			char[] str = words.toCharArray();
			Node2 node = root;
			node.pass++;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = (int)str[i];
				if(!node.nexts.containsKey(path)){
					node.nexts.put(path,new Node2());
				}
				node = node.nexts.get(path);
				node.pass++;
			}
			node.end++;
		}

		public int search(String words){
			if(words == null) return 0;

			char[] str = words.toCharArray();

			Node2 node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = (int)str[i];
				if(!node.nexts.containsKey(path)){
					return 0;
				}
				node = node.nexts.get((path));
			}
			return  node.end;
		}

		public int prefixNumber(String words){
			if(words == null) return 0;

			char[] str = words.toCharArray();
			Node2 node = root;
			int path = 0;
			for(int i =0;i<str.length;++i){
				path = (int)str[i];
				if(!node.nexts.containsKey(path)){
					return 0;
				}
				node = node.nexts.get(path);
			}
			return node.pass;
		}

		public void delete(String words){
			if(words==null) return;
			if(search(words)!=0){
				char[] str = words.toCharArray();
				Node2 node = root;
				node.pass--;
				int path = 0;
				for(int i =0;i<str.length;++i){
					path = (int)str[i];
					if(--node.nexts.get(path).pass==0){
						node.nexts.remove(path);
						return;
					}
					node = node.nexts.get(path);
				}
				node.end--;
			}
		}

	}



	public static class Right {

		private HashMap<String, Integer> box;

		public Right() {
			box = new HashMap<>();
		}

		public void insert(String word) {
			if (!box.containsKey(word)) {
				box.put(word, 1);
			} else {
				box.put(word, box.get(word) + 1);
			}
		}

		public void delete(String word) {
			if (box.containsKey(word)) {
				if (box.get(word) == 1) {
					box.remove(word);
				} else {
					box.put(word, box.get(word) - 1);
				}
			}
		}

		public int search(String word) {
			if (!box.containsKey(word)) {
				return 0;
			} else {
				return box.get(word);
			}
		}

		public int prefixNumber(String pre) {
			int count = 0;
			for (String cur : box.keySet()) {
				if (cur.startsWith(pre)) {
					count += box.get(cur);
				}
			}
			return count;
		}
	}

	// for test
	public static String generateRandomString(int strLen) {
		char[] ans = new char[(int) (Math.random() * strLen) + 1];
		for (int i = 0; i < ans.length; i++) {
			int value = (int) (Math.random() * 6);
			ans[i] = (char) (97 + value);
		}
		return String.valueOf(ans);
	}

	// for test
	public static String[] generateRandomStringArray(int arrLen, int strLen) {
		String[] ans = new String[(int) (Math.random() * arrLen) + 1];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = generateRandomString(strLen);
		}
		return ans;
	}

	public static void main(String[] args) {
		int arrLen = 100;
		int strLen = 20;
		int testTimes = 100000;
		for (int i = 0; i < testTimes; i++) {
			String[] arr = generateRandomStringArray(arrLen, strLen);
			Trie trie1 = new Trie();
			Tire2 trie2 = new Tire2();
			Right right = new Right();
			for (int j = 0; j < arr.length; j++) {
				double decide = Math.random();
				if (decide < 0.25) {
					trie1.insert(arr[j]);
					trie2.insert(arr[j]);
					right.insert(arr[j]);
				} else if (decide < 0.5) {
					trie1.delete(arr[j]);
					trie2.delete(arr[j]);
					right.delete(arr[j]);
				} else if (decide < 0.75) {
					int ans1 = trie1.search(arr[j]);
					int ans2 = trie2.search(arr[j]);
					int ans3 = right.search(arr[j]);
					if (ans1 != ans2 || ans2 != ans3) {
						System.out.println("Oops!");
					}
				} else {
					int ans1 = trie1.prefixNumber(arr[j]);
					int ans2 = trie2.prefixNumber(arr[j]);
					int ans3 = right.prefixNumber(arr[j]);
					if (ans1 != ans2 || ans2 != ans3) {
						System.out.println("Oops!");
					}
				}
			}
		}
		System.out.println("finish!");

	}

}